package alo.p19;

/**
 * @ClassName CatalanNumber
 * @Description 卡特兰数：n个结点的二叉搜索树总共有多少棵树呢？
 * @Author Fanxc
 * @DATE 2021/3/15 16:10
 * @Version 1.0
 */
public class CatalanNumber {
    int catalanNumber(int n){
        if (n==0){
            return 1;
        }
        int count=0;
        for (int i = 1; i < n; i++) {
            count+=catalanNumber(i-1)*catalanNumber(n-i);
        }
        return count;
    }
    int[] Table=new int[100];
    int catalanNumber2(int n){
        Table[1]=1;
        if (Table[n]!=0){//如果计算过了，直接返回
            return Table[n];
        }
        Table[n]=0;
        for (int i = 1; i <= n ; i++) {
            Table[n]+=catalanNumber2(i-1)*catalanNumber2(n-i);
        }
        return Table[n];
    }

}
